#include <iostream>
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <math.h>

using namespace std;
double b;
double rd()
{
    // 创建随机数生成器
    random_device rd;
    mt19937 gen(rd());
    // 创建随机数分布器
    uniform_real_distribution<> dis(0, 1);
    // 生成随机数
    double n = dis(gen);
    return n;
}

class GridPoint
{
public:
    double load;
    double capacity;
    double free_space;
    GridPoint(double x, double y) : load(x), free_space(y)
    {
        capacity = x + y;
    }
};

bool cmp(const GridPoint &p1, const GridPoint &p2)
{
    double beta = b;
    return p1.load * pow(p1.free_space, beta) > p2.load * pow(p2.free_space, beta);
}

class net
{
private:
public:
    int size = 5000;
    vector<GridPoint> list;
    double tload, tfree, tcapacity;
    net()
    {
        tload = 0;
        tfree = 0;
        for (int i = 0; i < size; i++)
        {
            double l = rd() * 20 + 10.0;
            double f = rd() * 50 + 10.0;
            tload += l;
            tfree += f;
            GridPoint p(l, f);
            list.push_back(p);
        }
        // cout << "Generating OK..." << endl;
    }

    void Rank() // 从大到小排序
    {
        sort(list.begin(), list.end(), cmp);
    }

    void Collapse(double d)
    {
        // cout << "Collapsing..." << endl;
        double collapse_load = 0;
        for (int i = 0; i < list.size(); i++) // 所有load全部加上重新分配的d
        {
            list[i].load += d;
        }
        for (auto it = list.begin(); it != list.end();)
        {
            if ((*it).load > (*it).capacity)
            {
                collapse_load += (*it).load;
                list.erase(it);
            }
            else
            {
                it++;
            }
        }
        // cout << "Total loads needs to be reloaded: " << collapse_load << endl;
        // cout << "And there are " << list.size() << " alive" << endl;
        if (collapse_load != 0)
            Collapse(collapse_load / list.size());
    }

    void Fail(int k) // 被摧毁的k个线导致从load重新分布
    {
        double tmp;
        for (int i = 0; i < k; i++)
        {
            tmp += list[i].load;
        }

        auto it = list.begin();
        list.erase(it, it + k - 1);
        tmp = tmp / list.size();
        // cout << "Attack is OK..." << endl;
        Collapse(tmp);
    }
};

int compute(int k)
{
    net NET;
    NET.Rank();
    NET.Fail(k);
    return NET.list.size();
}

int main()
{
    vector<int> betabreak;
    // cout << 1550 << ", " << compute(1630) << endl;
    for (int k = 0; k <= 20; k++)
    {
        int as = 0;
        b = k * 0.1;
        for (int i = 1; i <= 100; i++)
        {
            int ave = 0;
            for (int j = 0; j < 10; j++)
            {
                // cout << ".";
                ave += compute(i * 20);
            }
            ave = ave / 10;
            if (ave == 0 && as == 0)
            {
                as = i * 20;
                betabreak.push_back(as);
                cout << as << endl;
            }
        }
    }

    cout << "y1 = [";
    for (int i = 0; i <= 20; i++)
    {
        cout << betabreak[i] << ", ";
    }
    cout << "];" << endl;
    cout << "x = 0:0.1:2;" << endl;

    cout << "plot(x, y1, '-*')" << endl;

    return 0;
}
// y1 = [1680, 1540, 1440, 1440, 1460, 1460, 1500, 1480, 1520, 1520, 1520, 1540, 1540, 1560, 1580, 1560, 1560, 1580, 1600, 1580, 1600, ];
// x = 0:0.1:2;
// plot(x, y1, '-*')

